package com.example.demo.shuatiban.zuocheng;

/**
 * @author xujm
 * @version V2.4
 *
 *  给定一个字符串 str1 = aabb
 *  给定一个字符串 str2 = a2bc
 *
 *  求 str3=aaa2bbbc 是否由str1 str2交错组成
 *
 * @since 2.4.0 2022/3/27 15:17
 */
public class 字符串交错组成 {

    /**
     * 使用样本对应模型
     *  定义dp[i][j],表示str i+j (下标0 ~ i+j-1) 前个数 是否由 str1 i(0~i-1)前个数 和 str2 j(0~j-1)前个数组成
     *
     *
     *   str1 str2 0   1   2   3   4   5
     *    0        T   T   T   F   F   F
     *    1        T
     *    2        F       ?
     *    3        F
     *    4        F
     *    5        F
     *    中间值如何判断?
     *    求dp[i][j] 是否存在str 由str1 str2组成的数
     *      str1 标识横坐标 ，下标 i
     *    如果 str1[i-1] == str[i+j-1]  那么 dp[i-1][j]为true标识存在结果
     *
     *    如果 str2[j-1] == str[i+j-1] 那么 dp[i][j-1]为true则表示存在结果
     *
     * @param str1
     * @param str2
     * @param str
     * @return
     */
    public static boolean judge(String str1,String str2,String str){

        if(str.length() != (str1.length()+str2.length())){
            return false;
        }

        char[] chars2 = str2.toCharArray();
        char[] chars1 = str1.toCharArray();
        char[] chars = str.toCharArray();

        boolean [][] dp = new boolean [chars1.length+1][chars2.length+1];

        dp[0][0]= true;
        boolean fail = false;//出现一次匹配不上，后面都是false
        for(int i=1;i<chars2.length;i++){
            if(!fail && (chars2[i-1] == chars[i-1])){
                dp[0][i] = true;
            }else{
                fail = true;
                dp[0][i] = false;
            }
        }

        fail = false;
        for(int i=1;i<chars1.length;i++){
            if(!fail && (chars1[i-1] == chars[i-1])){
                dp[i][0] = true;
            }else{
                fail = true;
                dp[i][0] = false;
            }
        }

        for(int i=1;i<=chars1.length;i++){
            for(int j=1;j<=chars2.length;j++){

                if((chars1[i-1] == chars[i+j-1]) && dp[i-1][j]){
                    dp[i][j] = true;
                }
                else if((chars2[j-1] == chars[i+j-1]) && dp[i][j-1]){
                    dp[i][j] = true;
                }
                else{
                    dp[i][j] = false;
                }

            }
        }
        return dp[chars1.length][chars2.length];
    }

    public static void main(String[] args) {


 // *  给定一个字符串 str1 = aabb
 //            *  给定一个字符串 str2 = a2bc
 //            *
 // *  求 str3=aaa2bbbc 是否由str1 str2交错组成
        String str1 = "aabb";
        String str2 = "a2bc";
        String str = "aaa2bbbc";

        System.out.println(judge(str1,str2,str));
    }

}
